package annotool.select;

public class QuickSort

{
	       
	public static void sort(float array[], float s[][], int start, int end)
	{
		
	        int i = start;                          // index of left-to-right scan
	        int k = end;                            // index of right-to-left scan

	        if (end - start >= 1)                   // check that there are at least two elements to sort
	        {
	                float pivot = array[start];       // set the pivot as the first element in the partition

	                while (k > i)                   // while the scan indices from left and right have not met,
	                {
	                        while (array[i] <= pivot && i <= end && k > i)  // from the left, look for the first
	                                i++;                                    // element greater than the pivot
	                        while (array[k] > pivot && k >= start && k >= i) // from the right, look for the first
	                            k--;                                        // element not greater than the pivot
	                        if (k > i)                                       // if the left seekindex is still smaller than
	                                swap(array,  s, i, k);                      // the right index, swap the corresponding elements
	                }
	                swap(array,  s, start, k);          // after the indices have crossed, swap the last element in
	                                                // the left partition with the pivot 
	                sort(array,  s, start, k - 1); // quicksort the left partition
	                sort(array,  s, k + 1, end);   // quicksort the right partition
	        }
	        else    // if there is only one element in the partition, do not do any sorting
	        {
	                return;                     // the array is sorted, so exit
	        }
	}



	public static void swap(float array[], float s[][], int index1, int index2) 
	// pre: array is full and index1, index2 < array.length
	// post: the values at indices 1 and 2 have been swapped
	{
		float temp = array[index1];           // store the first value in a temp
		float[] a1 = s[index1];
		array[index1] = array[index2];      // copy the value of the second into the first
		s[index1] = s[index2];
		array[index2] = temp;               // copy the value of the temp into the second
		s[index2] = a1;
	}

}